Parallel processing techniques divide jobs among at least two separate processors to gain computational efficiencies when operating on a large group of data, called a load or job. It is often more efficient, where possible, to divide a job for concurrent processing among multiple processors in order to complete the computations in a shorter period of time. Loads to be processed can either be characterized as indivisible or divisible. An indivisible load is one that cannot be divided into two or more smaller fragments to be distributed among multiple processors but requires that the load be processed by a single processor. A divisible load is a load that can be arbitrarily partitioned in a linear fashion and can be distributed to more than one processor to achieve a faster solution time. An example of a divisible load is a very long linear data file associated with a simple operation such as the summation of a large set of numbers. Intermediate sums of the list of numbers can be computed on different distributed processors and then later recombined and added together to gain the final solution.
A more sophisticated example of a divisible load is data representing an input waveform which is to be applied to a series of digital filters to identify the waveform. The data can be segmented and processed on different processors in order to expedite the required computation period. In general, the class of divisible loads includes problems where a number of repetitive and independent operations are performed on very large data files. Examples of divisible loads commonly appear in the areas of signal processing, image processing and experimental data processing. Divisible load theory has the benefit of being completely deterministic without requiring any statistical or probabilistic assumptions.
When a divisible load is distributed to a number of processors, there is a need for a central controller, which can be one of the processors, to select which processor gets which portion of the load and in what order. One scheme is to assign the fastest processor (in terms of computational speed) with as much data as possible within a given time constraint. This speed based load sharing approach must take into account the number of available processors, the speed of each processor, the speed of the communication links, the load origination point and the network architecture.
Previous allocations of controllers have been based upon processor speed among networked processors in order to gain time efficiencies by parallel processing the divisible load. As computer hardware and communications technology are quickly advancing, an opportunity to link processors located at different remote sites together to compute a load is promising. The internet currently allows for the fast and cheap communication between processors irrespective of their physical locations. Indeed, the internet allows for worldwide communication on a relatively inexpensive basis.
Communication costs (e.g., telephone line charges) are one of the monetary costs associated with distributed processing. Different processors also have varied associated monetary costs themselves. One minute of processor time on a super-computer is many orders of magnitude more expensive to operate than on a simple 486 computer platform. Businesses now have the capability of renting out their idle processor time to other users when connected in a global network such as the internet. Ross Perot, founder of Electronic Data Systems of Texas, made a business out of renting idle time on private mainframe computer installations to run programming. The increased number of different types of processors with varied associated monetary costs creates a need for a load sharing controller which assigns divisible loads among distributed processors to minimize the overall monetary cost to process the load.